package summary;

import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/7 11:55
 */
public class Title85 {

    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[] height = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    height[j] += 1;
                }else{
                    height[j] = 0;
                }
            }
            max = Math.max(max, getRowRectangle(height));
        }
        return max;
    }

    private int getRowRectangle(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int[] newheight = new int[height.length + 2];
        for (int i = 0; i < height.length; i++) {
            newheight[i + 1] = height[i];
        }
        int max = 0;
        for (int i = 0; i < newheight.length; i++) {
            while (!stack.isEmpty() && newheight[i] < newheight[stack.peek()]) {
                Integer mid = stack.pop();
                Integer left = stack.peek();
                int h = i - left - 1;
                int w = newheight[mid];
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }

    public static void main(String[] args) {

    }
}
